package leetCode.function;

/**
 * 假设有排成一行的N个位置，记为1~N，N一定大于或等于2;
 * 开始时机器人在M（1 <= M <= N）位置上，
 * 如果机器人位于1位置，那么下一步只能走到2位置，
 * 如果机器人位于N位置，那么下一步只能走到N-1位置，
 * 如果机器人位于中间的任一位子，那么下一步可以向左走，也可以向右走。
 * 机器人必须走K步，最终来到P（1 <= P <= N），给定参数N，M，K，P，有多少种走法？
 **/
public class RobotWalk {
    
    
    public static void main(String[] args) {
    	long start1 = System.currentTimeMillis();
        System.out.println("暴力递归法答案：" + way1(5, 3, 37, 4) + " " + (System.currentTimeMillis()-start1));
        long start2 = System.currentTimeMillis();
        System.out.println("暴力递归缓存法答案：" + way2(5, 3, 37, 4) + " " + (System.currentTimeMillis()-start2));
        long start3 = System.currentTimeMillis();
        System.out.println("动态规划法答案：" + way3(5, 3, 37, 4) + " " + (System.currentTimeMillis()-start3));
    }
    
    /**
     * 暴力递归法
     * @param n N个位置
     * @param m 开始时机器人在M（1 <= M <= N）位置上
     * @param k 必须走K步
     * @param p 目标位置p
     * @return 方案数
     */
    public static int way1(int n, int m, int k, int p) {
        return fun1(k, m, n, p);
    }

    /**
     * 从cur位置走rest步到达p位置的方法数
     * @param rest 剩余步数
     * @param cur 当前位置
     * @param n 位置数
     * @param p 目标位置
     * @return 从cur位置走rest步到达p位置的方法数
     */
    public static int fun1(int rest, int cur, int n, int p) {
        // 步数已走完，且当前处于目标位置上，则属于一种方法
        if (rest == 0) {
            return cur == p ? 1 : 0;
        }
        if (cur == 1) {
            // 位于1位置，只能走到2
            return fun1(rest - 1, 2, n, p);
        } else if (cur == n) {
            // 位于n位置，只能走到n-1
            return fun1(rest - 1, n - 1, n, p);
        } else {
            // 位于中间位置，可向左走也可向右走
            return fun1(rest - 1, cur + 1, n, p) + fun1(rest - 1, cur - 1, n, p);
        }
    }

    /**
     * 暴力递归法 + 缓存
     * @param n N个位置
     * @param m 开始时机器人在M（1 <= M <= N）位置上
     * @param k 必须走K步
     * @param p 目标位置p
     * @return 方案数
     */
    public static int way2(int n, int m, int k, int p) {
        int[][] dp = new int[n+1][k+1];
        // 初始化缓存
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= k; j++) {
                dp[i][j] = -1;
            }
        }
        return fun2(k, m, n, p, dp);
    }

    /**
     * 从cur位置走rest步到达p位置的方法数
     * @param rest 剩余步数
     * @param cur 当前位置
     * @param n 位置数
     * @param p 目标位置
     * @return 从cur位置走rest步到达p位置的方法数
     */
    public static int fun2(int rest, int cur, int n, int p, int[][] dp) {
        // 已缓存，直接返回
        if (dp[cur][rest] != -1) {
            return dp[cur][rest];
        }
        // 步数已走完，且当前处于目标位置上，则属于一种方法
        if (rest == 0) {
            return cur == p ? 1 : 0;
        }
        int res = 0;
        if (cur == 1) {
            // 位于1位置，只能走到2
            res = fun2(rest - 1, 2, n, p, dp);
        } else if (cur == n) {
            // 位于n位置，只能走到n-1
            res = fun2(rest - 1, n - 1, n, p, dp);
        } else {
            // 位于中间位置，可向左走也可向右走
            res = fun2(rest - 1, cur + 1, n, p, dp) + fun2(rest - 1, cur - 1, n, p, dp);
        }
        dp[cur][rest] = res;
        return res;
    }

    /**
     * 动态规划
     * @param n N个位置
     * @param m 开始时机器人在M（1 <= M <= N）位置上
     * @param k 必须走K步
     * @param p 目标位置p
     * @return 方案数
     */
    public static int way3(int n, int m, int k, int p) {
        // cur rest
        int[][] dp = new int[n+1][k+1];
        dp[p][0] = 1;
        // rest循环 列循环
        for (int j = 1; j <= k; j++) {
            dp[1][j] = dp[2][j-1];
            // cur循环 行循环
            for (int i = 2; i < n; i++) {
                dp[i][j] = dp[i-1][j-1] + dp[i+1][j-1];
            }
            dp[n][j] = dp[n-1][j-1];
        }
        return dp[m][k];
    }

}
